package ClassicalSortingAlgorithm;

import java.util.ArrayList;
import java.util.List;

/**
 * @BelongsProject: LeetCode
 * @BelongsPackage: ClassicalSortingAlgorithm
 * @Author: song
 * @CreateTime: 2022-09-16  01:01
 * @Description: 基数排序：该算法属于稳定性算法，时间复杂度 ：最佳：O(n×k) 最差：O(n×k) 平均：O(n×k)
 * 空间复杂度 ：O(n+k)；
 * @Version: 1.0
 */

public class radixSort {
    public static void main(String[] args) {
        int[] nums = {2,8,97,45,456,21,34,6,78,65};
        radixSort(nums);
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i] + " ");
        }
    }

    public static int[] radixSort(int[] nums){
        if (nums.length < 2){
            return nums;
        }
        int N = 1; // 该变量记录数组中最高的位数；
        int maxValue = nums[0];
        // 这个循环选择出数组当中最大的数字；
        for (int num:nums) {
            if (maxValue < num){
                maxValue = num;
            }
        }
        // 计算该数组中最大的位数，也就是要循环的次数
        while (maxValue / 10 != 0){
            maxValue = maxValue / 10 ;
             N += 1 ;
        }
        for (int i = 0; i < N; i++) {
            ArrayList<List<Integer>> radix = new ArrayList<>();
            // 这一步是建立十个桶；
            for (int j = 1; j <= 10; j++) {
                radix.add(new ArrayList<Integer>());
            }
            // 这一步是计算每个数字放置的桶，
            for (int element:nums) {
                int idx = (element / (int)Math.pow(10,i)) % 10;
                radix.get(idx).add(element);
            }
            int idx = 0;
            for(List<Integer> l : radix){
                for (int num:l){
                    nums[idx++] = num;
                }
            }
        }

        return nums;
    }
}
